{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Changes to Make K Semi-palindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #two-pointers #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #双指针 #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumChanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到 K 个半回文串的最少修改次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，请你将&nbsp;<code>s</code> 分成&nbsp;<code>k</code>&nbsp;个<strong>&nbsp;子字符串</strong>&nbsp;，使得每个 <strong>子字符串</strong>&nbsp;变成&nbsp;<strong>半回文串</strong>&nbsp;需要修改的字符数目最少。</p>\n",
    "\n",
    "<p>请你返回一个整数，表示需要修改的 <strong>最少</strong>&nbsp;字符数目。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一个字符串从左往右和从右往左读是一样的，那么它是一个 <strong>回文串</strong>&nbsp;。</li>\n",
    "\t<li>如果长度为 <code>len</code>&nbsp;的字符串存在一个满足&nbsp;<code>1 &lt;= d &lt; len</code>&nbsp;的正整数&nbsp;<code>d</code>&nbsp;，<code>len % d == 0</code>&nbsp;成立且所有对 <code>d</code>&nbsp;做除法余数相同的下标对应的字符连起来得到的字符串都是 <strong>回文串</strong>&nbsp;，那么我们说这个字符串是 <strong>半回文串</strong>&nbsp;。比方说&nbsp;<code>\"aa\"</code>&nbsp;，<code>\"aba\"</code> ，<code>\"adbgad\"</code>&nbsp;和&nbsp;<code>\"abab\"</code>&nbsp;都是 <strong>半回文串</strong>&nbsp;，而&nbsp;<code>\"a\"</code>&nbsp;，<code>\"ab\"</code>&nbsp;和&nbsp;<code>\"abca\"</code>&nbsp;不是。</li>\n",
    "\t<li><strong>子字符串</strong>&nbsp;指的是一个字符串中一段连续的字符序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abcac\", k = 2\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>我们可以将 s 分成子字符串 \"ab\" 和 \"cac\" 。子字符串 \"cac\" 已经是半回文串。如果我们将 \"ab\" 变成 \"aa\" ，它也会变成一个 d = 1 的半回文串。\n",
    "该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"abcdef\", k = 2\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们可以将 s 分成子字符串 \"abc\" 和 \"def\" 。子字符串 \"abc\" 和 \"def\" 都需要修改一个字符得到半回文串，所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。\n",
    "该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aabbaa\", k = 3\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>我们可以将 s 分成子字符串 \"aa\" ，\"bb\" 和 \"aa\" 。\n",
    "字符串 \"aa\" 和 \"bb\" 都已经是半回文串了。所以答案为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= s.length &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length / 2</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-changes-to-make-k-semi-palindromes](https://leetcode.cn/problems/minimum-changes-to-make-k-semi-palindromes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-changes-to-make-k-semi-palindromes](https://leetcode.cn/problems/minimum-changes-to-make-k-semi-palindromes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcac\"\\n2', '\"abcdef\"\\n2', '\"aabbaa\"\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def helper(s):\n",
    "            i, j = 0, len(s) - 1\n",
    "            cnt = 0\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    cnt += 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return cnt\n",
    "\n",
    "\n",
    "        semi = {}\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                cand = s[i:j + 1]\n",
    "                rev = len(cand)\n",
    "                for d in range(1, len(cand)//2+1):\n",
    "                    if len(cand) % d: continue\n",
    "                    tmp = defaultdict(str)\n",
    "                    for idx in range(len(cand)):\n",
    "                        tmp[idx % d] += cand[idx]\n",
    "                    rev = min(rev, sum(helper(s) for s in tmp.values()))\n",
    "                semi[i, j] = rev\n",
    "\n",
    "\n",
    "        # semi[0, 2]+semi[3, 5]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if i >= n - 1:\n",
    "                return float('inf')\n",
    "            if k == 1:\n",
    "                return semi[i, n - 1]\n",
    "\n",
    "            ans = float('inf')\n",
    "            for j in range(i + 1, n):\n",
    "                ans = min(ans, semi[i, j] + dp(j + 1, k - 1))\n",
    "            return ans\n",
    "\n",
    "# dp(0, k)\n",
    "        \n",
    "        \n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 201\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i * 2, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "def get_modify(s: str) -> int:\n",
    "    res = n = len(s)\n",
    "    for d in divisors[n]:\n",
    "        cnt = 0\n",
    "        for i0 in range(d):\n",
    "            i, j = i0, n - d + i0\n",
    "            while i < j:\n",
    "                cnt += s[i] != s[j]\n",
    "                i += d\n",
    "                j -= d\n",
    "        res = min(res, cnt)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        modify = [[0] * n for _ in range(n - 1)]\n",
    "        for left in range(n - 1):\n",
    "            for right in range(left + 1, n):\n",
    "                modify[left][right] = get_modify(s[left: right + 1])\n",
    "\n",
    "        f = modify[0]\n",
    "        for i in range(1, k):\n",
    "            for j in range(n - 1 - (k - 1 - i) * 2, i * 2, -1):  # 左右都要预留空间\n",
    "                f[j] = min(f[L - 1] + modify[L][j] for L in range(i * 2, j))\n",
    "        return f[-1]\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个数的真因子，时间复杂度 O(MX*logMX)\n",
    "MX = 201\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i * 2, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "def get_modify(s: str) -> int:\n",
    "    res = n = len(s)\n",
    "    for d in divisors[n]:\n",
    "        cnt = 0\n",
    "        for i0 in range(d):\n",
    "            i, j = i0, n - d + i0\n",
    "            while i < j:\n",
    "                cnt += s[i] != s[j]\n",
    "                i += d\n",
    "                j -= d\n",
    "        res = min(res, cnt)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        # modify = [[0] * n for _ in range(n - 1)]\n",
    "        # for left in range(n - 1):\n",
    "        #     for right in range(left + 1, n):  # 半回文串长度至少为 2\n",
    "        #         modify[left][right] = get_modify(s[left: right + 1])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i == 0:\n",
    "                return get_modify(s[0: j+1])\n",
    "            return min(dfs(i - 1, L - 1) + get_modify(s[L: j+1]) for L in range(i * 2, j))\n",
    "        return dfs(k - 1, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 201\n",
    "real = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i * 2, MX, i):\n",
    "        real[j].append(i)\n",
    "\n",
    "def get_cnt(s):\n",
    "    ans = inf\n",
    "    n = len(s)\n",
    "    for pace in real[n]:\n",
    "        cur = 0\n",
    "        for st in range(pace):\n",
    "            # 枚举长度n的真因数 看看将其修改为半回文串需要的修改次数\n",
    "            i, j = st, n - pace + st\n",
    "            while i < j:\n",
    "                if s[i] != s[j]:\n",
    "                    cur += 1\n",
    "                i += pace\n",
    "                j -= pace\n",
    "        ans = cur if cur < ans else ans\n",
    "    return ans\n",
    "                    \n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        data = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # 枚举所有的子串 让其变成半回文串需要的最少操作次数\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                data[i][j] = get_cnt(s[i:j+1])\n",
    "        # print(data)\n",
    "        @cache\n",
    "        def dfs(rest, i):\n",
    "            # 切rest刀 得到rest+1个子串 同时从0位置到i位置 最少需要修改多少字符\n",
    "            if rest == 0:\n",
    "                return data[0][i]\n",
    "            cur = inf\n",
    "            for split in range(rest * 2, i):\n",
    "                cur = min(cur, dfs(rest-1, split-1) + data[split][i])\n",
    "            return cur\n",
    "        ans = dfs(k-1, n-1)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "divisor = [[] for _ in range(201)]\n",
    "for p in range(1, 101):\n",
    "    for i in range(2 * p, 201, p):\n",
    "        divisor[i].append(p)\n",
    "\n",
    "class Solution(object):\n",
    "    def minimumChanges(self, s, k):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def get_cnt(s):\n",
    "            n = len(s)\n",
    "            res = n \n",
    "            for d in divisor[n]:\n",
    "                cur = 0\n",
    "                for i in range(d):\n",
    "                    start, end = i, n - d + i \n",
    "                    while start <= end:\n",
    "                        cur += s[start] != s[end]\n",
    "                        start += d \n",
    "                        end -= d \n",
    "                res = min(res, cur)\n",
    "            return res \n",
    "        n = len(s)\n",
    "        modify = [[0 for _ in range(n)] for _ in range(n - 1)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                modify[i][j] = get_cnt(s[i : j + 1])\n",
    "        print(modify)\n",
    "        @lru_cache(None)\n",
    "        def dfs(cut, idx):\n",
    "            if cut == 0:\n",
    "                return modify[0][idx]\n",
    "            return min(dfs(cut - 1, p - 1) + modify[p][idx] for p in range(2 * cut, idx))\n",
    "        return dfs(k - 1, n - 1)\n",
    "\n",
    "\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        \n",
    "        def is_palindrome(t):\n",
    "            for i in range(len(t) // 2):\n",
    "                if t[i] != t[-i - 1]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def cal_str2palindrome(t):\n",
    "            return sum(t[i] != t[-i - 1] for i in range(len(t) // 2))\n",
    "        \n",
    "        @cache\n",
    "        def cal(t):\n",
    "            res = cal_str2palindrome(t)\n",
    "            for d in range(2, len(t)):\n",
    "                if len(t) % d: continue\n",
    "                subs = [''] * d\n",
    "                for r in range(len(t)):\n",
    "                    subs[r % d] += t[r]\n",
    "                tot = sum(cal_str2palindrome(sub) for sub in subs)\n",
    "                res = min(res, tot)\n",
    "            return res\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, s, kk):\n",
    "            if kk == 1:\n",
    "                return cal(s[i:])\n",
    "            res = j - i\n",
    "            for k in range(i + 2, j - 2 * kk + 2 + 1):\n",
    "                res = min(res, cal(s[i:k]) + dfs(k, j, s, kk - 1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, len(s), s, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def factor(x):\n",
    "    p = 2\n",
    "    res = list()\n",
    "    while p * p <= x:\n",
    "        if x % p == 0:\n",
    "            while x % p == 0:\n",
    "                res.append(p)\n",
    "                x //= p\n",
    "        p += 1\n",
    "    if x != 1:\n",
    "        res.append(x)\n",
    "    return tuple(res)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        \n",
    "        def is_palindrome(t):\n",
    "            for i in range(len(t) // 2):\n",
    "                if t[i] != t[-i - 1]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def cal_str2palindrome(t):\n",
    "            return sum(t[i] != t[-i - 1] for i in range(len(t) // 2))\n",
    "        \n",
    "        @cache\n",
    "        def cal(t):\n",
    "            res = cal_str2palindrome(t)\n",
    "            a = factor(len(t))\n",
    "            i = j = (1 << len(a)) - 1\n",
    "            while True:\n",
    "                j = i & (j - 1)\n",
    "                if j == 0: break\n",
    "                d = 1\n",
    "                for k in range(len(a)):\n",
    "                    if j >> k & 1:\n",
    "                        d *= a[k]\n",
    "                subs = [''] * d\n",
    "                for r in range(len(t)):\n",
    "                    subs[r % d] += t[r]\n",
    "                tot = sum(cal_str2palindrome(sub) for sub in subs)\n",
    "                res = min(res, tot)\n",
    "            return res\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, s, kk):\n",
    "            if kk == 1:\n",
    "                if j - i == 2:\n",
    "                    return int(s[i] != s[i + 1])\n",
    "                elif j - i == 3:\n",
    "                    if is_palindrome(s[i:i + 3]):\n",
    "                        return 0\n",
    "                    return 1\n",
    "                return cal(s[i:])\n",
    "            res = j - i\n",
    "            for k in range(i + 2, j - 2 * kk + 2 + 1):\n",
    "                res = min(res, cal(s[i:k]) + dfs(k, j, s, kk - 1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, len(s), s, k)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @cache\n",
    "        def check(head: int, tail: int) -> int:\n",
    "            length = tail - head + 1\n",
    "            best = inf\n",
    "            for d in range(1, (length >> 1) + 1):\n",
    "                if length % d: continue\n",
    "                res = 0\n",
    "                for x in range(d):\n",
    "                    left, right = head + x, head + x + length - d\n",
    "                    while left < right:\n",
    "                        if s[left] != s[right]: res += 1\n",
    "                        left += d\n",
    "                        right -= d\n",
    "                best = min(best, res)\n",
    "            return best\n",
    "\n",
    "        @cache\n",
    "        def dp(head:int, k: int) -> int:\n",
    "            if k == 1: return check(head, n - 1)\n",
    "            best = inf\n",
    "            for tail in range(head + 1, n - (k - 1) * 2):\n",
    "                res = check(head, tail) + dp(tail + 1, k - 1)\n",
    "                best = min(best, res)\n",
    "            return best\n",
    "        \n",
    "        return dp(0, k)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        g = [[inf] * n for _ in range(n)]\n",
    "        for l in range(0, n):\n",
    "            for r in range(l, n):\n",
    "                le = r - l + 1\n",
    "                for d in range(1, le):\n",
    "                    if le % d == 0:\n",
    "                        cnt = 0\n",
    "                        for i in range(le):\n",
    "                            j = (le // d - 1 - i // d) * d + i % d\n",
    "                            \n",
    "                            if i >= j:\n",
    "                                break\n",
    "                            if s[l + i] != s[l + j]:\n",
    "                                cnt += 1\n",
    "                        g[l][r] = min(g[l][r], cnt)               \n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r, m):\n",
    "            if l > r:\n",
    "                return inf\n",
    "            if m == 1:\n",
    "                return g[l][r]\n",
    "            res = inf\n",
    "            for i in range(l, r + 1):\n",
    "                res = min(res, g[l][i] + dfs(i + 1, r, m - 1))\n",
    "            return res\n",
    "        return dfs(0, n - 1, k)\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MX = 201\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i * 2, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "@cache\n",
    "def get_modify(s: str) ->int:\n",
    "    n = len(s)\n",
    "    res = n\n",
    "    for d in divisors[n]:\n",
    "        diff = 0\n",
    "        for l in range(d):\n",
    "            r = n-d+l\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    diff += 1\n",
    "                l += d\n",
    "                r -= d\n",
    "        res = min(res, diff)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(r:int, c: int) ->int:\n",
    "            if c == 0:\n",
    "                return get_modify(s[:r+1])\n",
    "            return min(get_modify(s[l:r+1]) + dfs(l-1, c-1) for l in range(c*2, r))\n",
    "        return dfs(n-1, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 200 + 1\n",
    "factors = [[] for _ in range(M)]\n",
    "for i in range(1, M):\n",
    "    for j in range(i * 2, M, i):\n",
    "        factors[j].append(i)\n",
    "\n",
    "@lru_cache(None)\n",
    "def check(s):\n",
    "    n = len(s)\n",
    "    res = inf\n",
    "    for d in factors[n]:\n",
    "        cnt = 0\n",
    "        for i in range(d):\n",
    "            t = s[i::d]\n",
    "            for j in range(len(t) // 2):\n",
    "                cnt += t[j] != t[-1 - j]\n",
    "        res = min(res, cnt)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r, re):\n",
    "            if re == 1:\n",
    "                return check(s[l: r + 1])\n",
    "            \n",
    "            return min(dfs(l, i, 1) + dfs(i + 1, r, re - 1) for i in range(l + 1, r - re * 2 + 3))\n",
    "\n",
    "        ans = dfs(0, n - 1, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, K: int) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @cache\n",
    "        def minimum(i, j, d):\n",
    "            tmp = 0\n",
    "            length = j - i + 1\n",
    "            for x in range(d):\n",
    "                l = i + x\n",
    "                r = j - d + 1 + x\n",
    "                while l < r:\n",
    "                    if s[l] != s[r]:\n",
    "                        tmp += 1\n",
    "                    l += d\n",
    "                    r -= d\n",
    "            return tmp\n",
    "        dp2 = [[202] * n for j in range(n)]\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dp2[i][j] = inf\n",
    "                for d in range(1, j - i + 1):\n",
    "                    if (j - i + 1) % d != 0: continue\n",
    "                    tmp = minimum(i, j , d)\n",
    "                    dp2[i][j] = min(dp2[i][j], tmp)\n",
    "\n",
    "        dp = [[202]*n for i in range(K + 1)]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            dp[1][i] = dp2[0][i]\n",
    "        \n",
    "        for i in range(2, K + 1):\n",
    "            for j in range(i-1, n):\n",
    "                for k in range(i - 2, j-1):\n",
    "                    dp[i][j] = min(dp[i][j], dp[i-1][k] + dp2[k+1][j])\n",
    "        return dp[K][n-1]\n",
    "            \n",
    "                        \n",
    "                        \n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dp(length, count):\n",
    "            if count == 1: return d(0, length)\n",
    "            res = inf\n",
    "            for i in range(count - 1, length):\n",
    "                res = min(res, dp(i - 1, count - 1) + d(i, length))\n",
    "            return res\n",
    "\n",
    "        @cache\n",
    "        def d(start, end):\n",
    "            res = inf\n",
    "            for k in range(1, end - start + 1):\n",
    "                count = 0\n",
    "                if (end-start+1)%k!=0:continue\n",
    "                for j in range(start, min(end + 1, start + k)):\n",
    "                    n = 0\n",
    "                    s1 = ''\n",
    "                    while j + k * n <= end:\n",
    "                        s1 += s[j + k * n]\n",
    "                        n += 1\n",
    "                    n = len(s1)\n",
    "                    for i in range(n):\n",
    "                        if i != n - i - 1 and s1[i] != s1[n - i - 1]:\n",
    "                            count += 1\n",
    "                res = min(res, count >> 1)\n",
    "            return res\n",
    "\n",
    "        return dp(len(s) - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        div = defaultdict(lambda: [1])\n",
    "        n = len(s)\n",
    "        for d in range(2, n):\n",
    "             for v in range(d + d, n + 1, d):\n",
    "                div[v].append(d)\n",
    "\n",
    "        def change(i, j):\n",
    "            return min(semi(i, j, d) for d in div[j - i])\n",
    "\n",
    "        @cache\n",
    "        def semi(i, j, d):\n",
    "            if i >= j: return 0\n",
    "            return semi(i + d, j - d, d) + sum(s[i + ii] != s[j - d + ii] for ii in range(d))\n",
    "\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k == 1:\n",
    "                return change(0, i)\n",
    "            return min(dp(j, k - 1) + change(j, i) for j in range((k - 1) * 2, i - 1))\n",
    "\n",
    "        return dp(n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        def cal(s1, s2):\n",
    "            c = 0\n",
    "            n = len(s1)\n",
    "            for i in range(n // 2):\n",
    "                if s1[i] != s2[i]:\n",
    "                    c += 1\n",
    "            return c\n",
    "        \n",
    "        def check(s):\n",
    "            n = len(s)\n",
    "            if n == 1:\n",
    "                return float('inf')\n",
    "            ans = float('inf')\n",
    "            for k in range(1, n // 2 + 1):\n",
    "                if n % k == 0:\n",
    "                    c = sum(cal(s[j::k], s[j::k][::-1]) for j in range(k))\n",
    "                    if c == 0:\n",
    "                        return 0\n",
    "                    ans = min(ans, c)\n",
    "            return ans\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(index, bs):\n",
    "            if index == n:\n",
    "                if bs == k:\n",
    "                    return 0\n",
    "                return float('inf')\n",
    "            ans = float('inf')\n",
    "            for r in range(index, n):\n",
    "                if n - r < k - bs:\n",
    "                    break\n",
    "                ans = min(ans, v[index][r] + dfs(r + 1, bs + 1))\n",
    "            return ans\n",
    "        \n",
    "        n = len(s)\n",
    "        v = [[0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                v[i][j] = check(s[i: j+1])      \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        n = len(s)\n",
    "        def sum_alter(i,j,d):\n",
    "            ret = 0\n",
    "            # print('aaa', i, j, d, s[i:j])\n",
    "            for start in range(i, i+d):\n",
    "                left = start\n",
    "                right = left+(j-i-1)//d*d\n",
    "                # print(left, right, d, s[left:right+1:d])\n",
    "                while left<right:\n",
    "                    ret+=(s[left]!=s[right])\n",
    "                    left+=d\n",
    "                    right-=d\n",
    "            return ret\n",
    "        for i in range(n):\n",
    "            for j in range(i+2,n+1):\n",
    "                cur_min = inf\n",
    "                for d in range(1,j-i):\n",
    "                    if (j-i)%d!=0:\n",
    "                        continue\n",
    "                    cur = sum_alter(i,j,d)\n",
    "                    # print(i,j,d,cur)\n",
    "                    if cur<cur_min:                        \n",
    "                        cur_min = cur\n",
    "                    \n",
    "                dic[(i,j)] = cur_min\n",
    "\n",
    "        # print(dic)\n",
    "\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            ret = inf\n",
    "            if k>0 and n-i<2*k:\n",
    "                return ret\n",
    "            if k==1:\n",
    "                return dic[(i,n)]\n",
    "            for j in range(i+2,n-(k-1)*2+1):\n",
    "                ret = min(ret, dic[(i,j)]+dp(j,k-1))\n",
    "            return ret\n",
    "        \n",
    "        return dp(0,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "BAD = 0x7f7f7f7f7f7f7f\n",
    "\n",
    "\n",
    "\n",
    "def calc(ss: str):\n",
    "    n = len(ss)\n",
    "    i, j = 0, n-1\n",
    "    cnt = 0\n",
    "    while i < j:\n",
    "        if ss[i] != ss[j]:\n",
    "            cnt += 1\n",
    "        i, j = i+1, j-1\n",
    "\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "        div = [[] for i in range(201)]\n",
    "\n",
    "        for x in range(1, 201):\n",
    "            y = 2\n",
    "            while x*y <= 200:\n",
    "                div[x*y].append(x)\n",
    "                y += 1\n",
    "\n",
    "\n",
    "        xx = [[None]*201 for i in range(201)]\n",
    "        def get_min_change(ii, jj):\n",
    "            if xx[ii][jj] is not None:\n",
    "                return xx[ii][jj]\n",
    "\n",
    "            if jj < ii+1:\n",
    "                return False\n",
    "\n",
    "            length = jj - ii + 1\n",
    "\n",
    "            min_change = 0x7f7f7f7f\n",
    "            for d in div[length]:\n",
    "                change = 0\n",
    "                for st in range(ii, ii + d):\n",
    "                    p = st\n",
    "\n",
    "                    ss = \"\"\n",
    "                    while p <= jj:\n",
    "                        ss += s[p]\n",
    "                        p += d\n",
    "\n",
    "                    change += calc(ss)\n",
    "\n",
    "                min_change = min(min_change, change)\n",
    "\n",
    "            xx[ii][jj] = min_change\n",
    "            return min_change\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        cc = [[None]*201 for i in range(201)]\n",
    "        def dp(ii, kk)->int:\n",
    "            if cc[ii][kk] is not None:\n",
    "                return cc[ii][kk]\n",
    "\n",
    "\n",
    "            if ii == n:\n",
    "                if kk == 0:\n",
    "                    return 0\n",
    "                return BAD\n",
    "\n",
    "            if kk == 0:\n",
    "                return BAD\n",
    "\n",
    "\n",
    "            ans = BAD\n",
    "            for jj in range(ii+1, n):\n",
    "                if kk == 1 and jj != n-1:\n",
    "                    continue\n",
    "\n",
    "                min_change = get_min_change(ii, jj)\n",
    "                ans = min(ans, min_change + dp(jj+1, kk-1))\n",
    "\n",
    "            # print(ii, kk, ans)\n",
    "            cc[ii][kk] = ans\n",
    "            return ans\n",
    "\n",
    "        return dp(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        def f(i, j):\n",
    "            m = j - i + 1\n",
    "            ans = inf\n",
    "            for d in range(1, m):\n",
    "                if m % d != 0:\n",
    "                    continue\n",
    "                t = 0\n",
    "                for i0 in range(d):\n",
    "                    ss = s[i:j+1][i0::d]\n",
    "                    for idx in range(len(ss) // 2):\n",
    "                        t += 1 if ss[idx] != ss[len(ss) - 1 - idx] else 0\n",
    "                \n",
    "                ans = min(ans, t)\n",
    "            return ans\n",
    "                    \n",
    "        g = [[inf for _ in range(n)] for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                g[i][j] = f(i, j)\n",
    "        \n",
    "            \n",
    "        @cache\n",
    "        def dfs(i, t):\n",
    "            if i == 0 and t == 0:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for j in range(i):\n",
    "                ans = min(ans, dfs(j, t - 1) + g[j][i - 1])\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def dp1(i,j):\n",
    "            res = math.inf\n",
    "            l = j-i+1\n",
    "            for d in range(1,l):\n",
    "                if l%d==0:\n",
    "                    cur = 0\n",
    "                    for shift in range(d):\n",
    "                        s2 = s[i+shift:j+1:d]\n",
    "                        cur += sum(a!=b for a,b in zip(s2,s2[::-1])) // 2\n",
    "                    res = min(res,cur)\n",
    "            return res\n",
    "        @cache\n",
    "        def dp2(i,k):\n",
    "            if k==0 or i<0:\n",
    "                return 0 if k==0 and i<0 else math.inf\n",
    "            res = math.inf\n",
    "            for j in range(i):\n",
    "                cur = dp2(j-1,k-1) + dp1(j,i)\n",
    "                res = min(cur,res)\n",
    "            return res\n",
    "        return dp2(len(s)-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "divs = defaultdict(list)\n",
    "for i in range(1, 201):\n",
    "    for j in range(1, i):\n",
    "        if i % j == 0:\n",
    "            divs[i].append(j)\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "\n",
    "        def get_substring(s:str, d:int) -> List[int]:\n",
    "            res = []\n",
    "            for i in range(d):\n",
    "                p = i\n",
    "                tmp = ''\n",
    "                while p < len(s):\n",
    "                    tmp += s[p]\n",
    "                    p += d\n",
    "                res.append(tmp)\n",
    "            return res\n",
    "\n",
    "        def getCnts(i: int, j: int) -> int:\n",
    "            res = inf\n",
    "            sub = s[i:j + 1]\n",
    "            for d in divs[j - i + 1]:\n",
    "                cur = 0\n",
    "                substrs = get_substring(sub, d)\n",
    "                for substr in substrs:\n",
    "                    for left in range(len(substr) // 2):\n",
    "                        if substr[left] != substr[-1 - left]:\n",
    "                            cur += 1\n",
    "                res = min(res, cur)\n",
    "            return res\n",
    "\n",
    "        cnts = {}\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                cnts[(i, j)] = getCnts(i, j)\n",
    "\n",
    "\n",
    "        # 划分dp\n",
    "        # 从i往后考虑，划分j组\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if j == 1 and len(s) - i < 2: return inf\n",
    "            if j == 1:\n",
    "                return cnts[(i, len(s) - 1)]\n",
    "            # 每组至少2个数字，\n",
    "            res = inf\n",
    "            for l in range(i + 1, len(s)):\n",
    "                res = min(res, dfs(l + 1, j - 1) + cnts[(i, l)])\n",
    "            return res\n",
    "\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        div = defaultdict(lambda: [1])\n",
    "        n = len(s)\n",
    "        for d in range(2, n):\n",
    "             for v in range(d + d, n + 1, d):\n",
    "                div[v].append(d)\n",
    "\n",
    "        @cache\n",
    "        def change(i, j):\n",
    "            return min(semi(i, j, d) for d in div[j - i])\n",
    "\n",
    "        @cache\n",
    "        def semi(i, j, d):\n",
    "            if i >= j: return 0\n",
    "            return semi(i + d, j - d, d) + sum(s[i + ii] != s[j - d + ii] for ii in range(d))\n",
    "\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k == 1:\n",
    "                return change(0, i)\n",
    "            return min(dp(j, k - 1) + change(j, i) for j in range((k - 1) * 2, i - 1))\n",
    "\n",
    "        return dp(n, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        # 变为半回文的最少修改次数\n",
    "        def fn(s):\n",
    "            L = len(s)\n",
    "            lis = [1]\n",
    "            for i in range(2, int(sqrt(L)) + 1):\n",
    "                if L % i == 0:\n",
    "                    lis.append(i)\n",
    "                    lis.append(L // i)\n",
    "\n",
    "            ans = L - 1\n",
    "            for i in lis:\n",
    "                cnt = 0\n",
    "                for j in range(i):\n",
    "                    sub = s[j::i]\n",
    "                    len_ = len(sub)\n",
    "                    cnt += sum(a != b for a, b in zip(sub[:len_ // 2], sub[:len_ // 2 - (len_ & 1 == 0):-1]))\n",
    "                ans = min(cnt, ans)\n",
    "            return ans\n",
    "\n",
    "        subStrLis = {}\n",
    "        L = len(s)\n",
    "        for len_ in range(2, L + 1):\n",
    "            for i in range(L - len_ + 1):\n",
    "                subStrLis[(i, i + len_ - 1)] = fn(s[i:i + len_])\n",
    "\n",
    "        # print(subStrLis)\n",
    "\n",
    "        @cache\n",
    "        def dfs(idx, sur):\n",
    "            if idx == L:\n",
    "                if sur == 0: return 0\n",
    "                return inf\n",
    "            if L - idx < sur * 2: return inf\n",
    "            ans = inf\n",
    "            for i in range(idx + 1, L):\n",
    "                ans = min(ans, subStrLis[(idx, i)] + dfs(i + 1, sur - 1))\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fs = defaultdict(list)\n",
    "for i in range(2, 201):\n",
    "    for j in range(1, i):\n",
    "        if i % j == 0:\n",
    "            fs[i].append(j)\n",
    "#print(d)\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def getMinCnt(s): # 把s变成半回文串的最少修改次数\n",
    "            res = len(s)\n",
    "            for d in fs[len(s)]:\n",
    "                cnt = 0\n",
    "                for start in range(d): # 开始位置\n",
    "                    tmp_s = s[start:len(s):d]\n",
    "                    cnt1 = 0\n",
    "                    m = len(tmp_s)\n",
    "                    #print(tmp_s)\n",
    "                    for idx in range(m // 2):\n",
    "                        if tmp_s[idx] != tmp_s[m - 1 - idx]:\n",
    "                            cnt1 += 1\n",
    "                    cnt += cnt1\n",
    "                res = min(res, cnt)\n",
    "            return res\n",
    "        #print(getMinCnt('adbgad'))\n",
    "        @cache\n",
    "        def dfs(cur, rest): # 从cur开始剩下rest中划分\n",
    "            if n - cur < rest or n - cur == 1: # 子字符串不能是1， 1 <= d < len\n",
    "                return inf\n",
    "            if rest == 1:\n",
    "                return getMinCnt(s[cur:])\n",
    "            res = inf\n",
    "            for nxt in range(cur + 2, n + 1):\n",
    "                #print(s[cur:nxt])\n",
    "                res = min(res, dfs(nxt, rest - 1) + getMinCnt(s[cur:nxt]))\n",
    "            return res\n",
    "        return dfs(0, k)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fs = defaultdict(list)\n",
    "for i in range(2, 201):\n",
    "    for j in range(1, i):\n",
    "        if i % j == 0:\n",
    "            fs[i].append(j)\n",
    "#print(d)\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def getMinCnt(s): # 把s变成半回文串的最少修改次数\n",
    "            res = len(s)\n",
    "            for d in fs[len(s)]:\n",
    "                cnt = 0\n",
    "                for start in range(d): # 开始位置\n",
    "                    tmp_s = s[start:len(s):d]\n",
    "                    cnt1 = 0\n",
    "                    m = len(tmp_s)\n",
    "                    #print(tmp_s)\n",
    "                    for idx in range(m // 2):\n",
    "                        if tmp_s[idx] != tmp_s[m - 1 - idx]:\n",
    "                            cnt1 += 1\n",
    "                    cnt += cnt1\n",
    "                res = min(res, cnt)\n",
    "            return res\n",
    "        #print(getMinCnt('adbgad'))\n",
    "        @cache\n",
    "        def dfs(cur, rest): # 从cur开始剩下rest中划分\n",
    "            if n - cur < rest or n - cur == 1: # 子字符串不能是1， 1 <= d < len\n",
    "                return inf\n",
    "            if rest == 1:\n",
    "                return getMinCnt(s[cur:])\n",
    "            res = inf\n",
    "            for nxt in range(cur + 2, n + 1):\n",
    "                #print(s[cur:nxt])\n",
    "                res = min(res, dfs(nxt, rest - 1) + getMinCnt(s[cur:nxt]))\n",
    "            return res\n",
    "        return dfs(0, k)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "BAD = 0x7f7f7f7f7f7f7f\n",
    "\n",
    "\n",
    "\n",
    "def calc(ss: str):\n",
    "    n = len(ss)\n",
    "    i, j = 0, n-1\n",
    "    cnt = 0\n",
    "    while i < j:\n",
    "        if ss[i] != ss[j]:\n",
    "            cnt += 1\n",
    "        i, j = i+1, j-1\n",
    "\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "        div = [[] for i in range(201)]\n",
    "\n",
    "        for x in range(1, 201):\n",
    "            y = 2\n",
    "            while x*y <= 200:\n",
    "                div[x*y].append(x)\n",
    "                y += 1\n",
    "\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def get_min_change(ii, jj):\n",
    "            if jj < ii+1:\n",
    "                return False\n",
    "\n",
    "            length = jj - ii + 1\n",
    "\n",
    "            min_change = 0x7f7f7f7f\n",
    "            for d in div[length]:\n",
    "                change = 0\n",
    "                for st in range(ii, ii + d):\n",
    "                    p = st\n",
    "\n",
    "                    ss = \"\"\n",
    "                    while p <= jj:\n",
    "                        ss += s[p]\n",
    "                        p += d\n",
    "\n",
    "                    change += calc(ss)\n",
    "\n",
    "                min_change = min(min_change, change)\n",
    "\n",
    "            return min_change\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        cc = [[None]*201 for i in range(201)]\n",
    "        def dp(ii, kk)->int:\n",
    "            if cc[ii][kk] is not None:\n",
    "                return cc[ii][kk]\n",
    "\n",
    "\n",
    "            if ii == n:\n",
    "                if kk == 0:\n",
    "                    return 0\n",
    "                return BAD\n",
    "\n",
    "            if kk == 0:\n",
    "                return BAD\n",
    "\n",
    "\n",
    "            ans = BAD\n",
    "            for jj in range(ii+1, n):\n",
    "                if kk == 1 and jj != n-1:\n",
    "                    continue\n",
    "\n",
    "                min_change = get_min_change(ii, jj)\n",
    "                ans = min(ans, min_change + dp(jj+1, kk-1))\n",
    "\n",
    "            # print(ii, kk, ans)\n",
    "            cc[ii][kk] = ans\n",
    "            return ans\n",
    "\n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "fac = [set() for _ in range(301)]\n",
    "for i in range(1, 301):\n",
    "    for j in range(1, i):\n",
    "        if i % j == 0:\n",
    "            fac[i].add(j)\n",
    "            if j != 1: fac[i].add(i // j)\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[inf] * n for _ in range(n)] \n",
    "\n",
    "        for l in range(n):\n",
    "            for r in range(l + 1, n):\n",
    "                m = r - l + 1\n",
    "                for z in fac[m]:\n",
    "                    cos = 0\n",
    "                    for j in range(m):\n",
    "                        jb = (m // z - 1 - j // z) * z + j % z\n",
    "                        if jb <= j: break\n",
    "                        cos += s[l + j] != s[l + jb]\n",
    "\n",
    "\n",
    "\n",
    "                    dp[l][r] = min(cos, dp[l][r])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(l, r, k):\n",
    "            if k == 1: return dp[l][r]\n",
    "            res = inf\n",
    "            for i in range(l + 1, r):\n",
    "                res = min(res, dfs(l, i, k-1) + dfs(i + 1, r, 1))\n",
    "            return res\n",
    "        return dfs(0, n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def check(s):\n",
    "            n = len(s)\n",
    "            res = inf\n",
    "            for i in range(1, n // 2 + 1):\n",
    "                if n % i:\n",
    "                    continue\n",
    "                num = 0\n",
    "                for k in range(i):\n",
    "                    x = ''\n",
    "                    for j in range(k, n, i):\n",
    "                        x += s[j]\n",
    "                    l, r = 0, len(x)-1\n",
    "                    while l < r:\n",
    "                        if x[l] != x[r]:\n",
    "                            num += 1\n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "                res = min(res, num)\n",
    "            return res\n",
    "        \n",
    "        @cache\n",
    "        def dfs(s, k):\n",
    "            if k == 1:\n",
    "                return check(s)\n",
    "            res = inf\n",
    "            for i in range(1, len(s)-1):\n",
    "                res = min(res, check(s[:i]) + dfs(s[i:], k-1))\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(s, k)\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "restNum = [[] for i in range(201)]\n",
    "for i in range(1, 201):\n",
    "    for j in range(2, 201):\n",
    "        if i * j > 200: break\n",
    "        restNum[i * j].append(i)\n",
    "\n",
    "@cache\n",
    "def getCount(s):\n",
    "    n = len(s)\n",
    "    minCount = inf\n",
    "    for d in restNum[n]:\n",
    "        sumCount = 0\n",
    "        for st in range(d):\n",
    "            t = s[st::d] \n",
    "            left, right = 0, len(t) - 1\n",
    "            while left < right:\n",
    "                if t[left] != t[right]:\n",
    "                    sumCount += 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        minCount = min(minCount, sumCount)\n",
    "    return minCount\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "\n",
    "        @cache \n",
    "        def dp(index, k):\n",
    "            if k == 0: \n",
    "                return getCount(s[index:])\n",
    "            c = inf\n",
    "            for i in range(index + 1, n - 2):\n",
    "                c = min(c, dp(i + 1, k - 1) + getCount(s[index:i + 1]))\n",
    "            return c\n",
    "            \n",
    "        return dp(0, k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]\n",
    "\n",
    "@cache\n",
    "def get_factors(n):    \n",
    "    s = (set(reduce(list.__add__, \n",
    "                ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))\n",
    "    s.remove(n)\n",
    "    return list(s)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def get(s,start, end):\n",
    "            res = float(\"inf\")\n",
    "            for factor in get_factors(end - start):\n",
    "                sm = 0\n",
    "                for shift in range(factor):\n",
    "                    l = start + shift\n",
    "                    r = end - factor + shift\n",
    "                    while l < r:\n",
    "                        if s[l] != s[r]:\n",
    "                            sm += 1\n",
    "                        l += factor\n",
    "                        r -= factor\n",
    "                res = min(res, sm)\n",
    "                if res == 0:\n",
    "                    break\n",
    "            return res\n",
    "\n",
    "        s = s\n",
    "        k = k\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,cnt):\n",
    "            if i == len(s):\n",
    "                if cnt == k:return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            res = inf\n",
    "            for j in range(i+1,len(s)+1):\n",
    "                res = min(res,get(s,i,j)+dfs(j,cnt+1))\n",
    "            return res\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "BAD = 0x7f7f7f7f7f7f7f\n",
    "\n",
    "\n",
    "\n",
    "def calc(ss: str):\n",
    "    n = len(ss)\n",
    "    i, j = 0, n-1\n",
    "    cnt = 0\n",
    "    while i < j:\n",
    "        if ss[i] != ss[j]:\n",
    "            cnt += 1\n",
    "        i, j = i+1, j-1\n",
    "\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "        div = [[] for i in range(201)]\n",
    "\n",
    "        for x in range(1, 201):\n",
    "            y = 2\n",
    "            while x*y <= 200:\n",
    "                div[x*y].append(x)\n",
    "                y += 1\n",
    "\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def get_min_change(ii, jj):\n",
    "            if jj < ii+1:\n",
    "                return False\n",
    "\n",
    "            length = jj - ii + 1\n",
    "\n",
    "            min_change = 0x7f7f7f7f\n",
    "            for d in div[length]:\n",
    "                change = 0\n",
    "                for st in range(ii, ii + d):\n",
    "                    p = st\n",
    "\n",
    "                    ss = \"\"\n",
    "                    while p <= jj:\n",
    "                        ss += s[p]\n",
    "                        p += d\n",
    "\n",
    "                    change += calc(ss)\n",
    "\n",
    "                min_change = min(min_change, change)\n",
    "\n",
    "            return min_change\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        cc = {}\n",
    "        def dp(ii, kk)->int:\n",
    "            if (ii, kk) in cc:\n",
    "                return cc[(ii, kk)]\n",
    "\n",
    "            if ii == n:\n",
    "                if kk == 0:\n",
    "                    return 0\n",
    "                return BAD\n",
    "\n",
    "            if kk == 0:\n",
    "                return BAD\n",
    "\n",
    "\n",
    "            ans = BAD\n",
    "            for jj in range(ii+1, n):\n",
    "                if kk == 1 and jj != n-1:\n",
    "                    continue\n",
    "\n",
    "                min_change = get_min_change(ii, jj)\n",
    "                ans = min(ans, min_change + dp(jj+1, kk-1))\n",
    "\n",
    "            # print(ii, kk, ans)\n",
    "            cc[(ii, kk)] = ans\n",
    "            return ans\n",
    "\n",
    "        return dp(0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "BAD = 0x7f7f7f7f7f7f7f\n",
    "\n",
    "\n",
    "\n",
    "def calc(ss: str):\n",
    "    n = len(ss)\n",
    "    i, j = 0, n-1\n",
    "    cnt = 0\n",
    "    while i < j:\n",
    "        if ss[i] != ss[j]:\n",
    "            cnt += 1\n",
    "        i, j = i+1, j-1\n",
    "\n",
    "    return cnt\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "\n",
    "        div = [[] for i in range(201)]\n",
    "\n",
    "        for x in range(1, 201):\n",
    "            y = 2\n",
    "            while x*y <= 200:\n",
    "                div[x*y].append(x)\n",
    "                y += 1\n",
    "\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def get_min_change(ii, jj):\n",
    "            if jj < ii+1:\n",
    "                return False\n",
    "\n",
    "            length = jj - ii + 1\n",
    "\n",
    "            min_change = 0x7f7f7f7f\n",
    "            for d in div[length]:\n",
    "                change = 0\n",
    "                for st in range(ii, ii + d):\n",
    "                    p = st\n",
    "\n",
    "                    ss = \"\"\n",
    "                    while p <= jj:\n",
    "                        ss += s[p]\n",
    "                        p += d\n",
    "\n",
    "                    change += calc(ss)\n",
    "\n",
    "                min_change = min(min_change, change)\n",
    "\n",
    "            return min_change\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        @lru_cache(typed=False, maxsize=12800000)\n",
    "        def dp(ii, kk)->int:\n",
    "            if ii == n:\n",
    "                if kk == 0:\n",
    "                    return 0\n",
    "                return BAD\n",
    "\n",
    "            if kk == 0:\n",
    "                return BAD\n",
    "\n",
    "\n",
    "            ans = BAD\n",
    "            for jj in range(ii+1, n):\n",
    "                if kk == 1 and jj != n-1:\n",
    "                    continue\n",
    "\n",
    "                min_change = get_min_change(ii, jj)\n",
    "                ans = min(ans, min_change + dp(jj+1, kk-1))\n",
    "\n",
    "            # print(ii, kk, ans)\n",
    "            return ans\n",
    "\n",
    "        return dp(0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def check(i, j):\n",
    "            if i == j:\n",
    "                return inf\n",
    "            tmp = s[i : j + 1]\n",
    "            if tmp == tmp[::-1]:\n",
    "                return 0\n",
    "            n = len(tmp)\n",
    "            res = inf\n",
    "            for d in range(1, n):\n",
    "                if n % d == 0:\n",
    "                    tmp_n = n // d\n",
    "                    x = 0\n",
    "                    for start in range(d):\n",
    "                        cur = tmp[start::d]\n",
    "\n",
    "                        for i in range(tmp_n // 2):\n",
    "                            x += int(cur[i] != cur[tmp_n - 1 - i])\n",
    "                    res = min(res, x)\n",
    "\n",
    "            return res\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, k: int):\n",
    "            if i == -1:\n",
    "                return 0 if k == 0 else inf\n",
    "            res = inf\n",
    "            for j in range(i + 1):\n",
    "                res = min(res, check(j, i) + dfs(j - 1, k - 1))\n",
    "            return res\n",
    "\n",
    "        return dfs(n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://space.bilibili.com/206214\n",
    "MX = 201\n",
    "divisors = [[] for _ in range(MX)]\n",
    "for i in range(1, MX):\n",
    "    for j in range(i * 2, MX, i):\n",
    "        divisors[j].append(i)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def semi(i: int, j: int, d: int) -> int:\n",
    "            if i >= j: \n",
    "                return 0\n",
    "            return semi(i + d, j - d, d) + sum(s[i + k] != s[j - d + k] for k in range(d))\n",
    "\n",
    "        n = len(s)\n",
    "        modify = [[0] * n for _ in range(n - 1)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                modify[i][j] = min(semi(i, j + 1, d) for d in divisors[j - i + 1])\n",
    "\n",
    "        f = modify[0]\n",
    "        for i in range(1, k):\n",
    "            for j in range(n - 1 - (k - 1 - i) * 2, i * 2, -1):  # 左右都要预留空间\n",
    "                f[j] = min(f[L - 1] + modify[L][j] for L in range(i * 2, j))\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 200 + 1\n",
    "factors = [[] for _ in range(M)]\n",
    "for i in range(1, M):\n",
    "    for j in range(i * 2, M, i):\n",
    "        factors[j].append(i)\n",
    "\n",
    "@lru_cache(None)\n",
    "def check(s):\n",
    "    n = len(s)\n",
    "    res = inf\n",
    "    for d in factors[n]:\n",
    "        cnt = 0\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dic[i % d].append(s[i])\n",
    "        for v in dic.values():\n",
    "            l, r = 0, len(v) - 1\n",
    "            while l < r:\n",
    "                cnt += v[l] != v[r]\n",
    "                l += 1\n",
    "                r -= 1\n",
    "        res = min(res, cnt)\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        f = [[inf] * n for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                f[i][j] = check(s[i: j + 1])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, re):\n",
    "            if re >= n - idx:\n",
    "                return inf\n",
    "            if re == 1:\n",
    "                return f[idx][-1]\n",
    "\n",
    "            return min(f[idx][i] + dfs(i + 1, re - 1) for i in range(idx + 1, n))\n",
    "\n",
    "        ans = dfs(0, k)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "restNum = [[] for i in range(201)]\n",
    "for i in range(1, 201):\n",
    "    for j in range(2, 201):\n",
    "        if i * j > 200: break\n",
    "        restNum[i * j].append(i)\n",
    "\n",
    "@cache\n",
    "def getCount(s):\n",
    "    n = len(s)\n",
    "    minCount = inf\n",
    "    for d in restNum[n]:\n",
    "        sumCount = 0\n",
    "        for st in range(d):\n",
    "            t = s[st::d] \n",
    "            left, right = 0, len(t) - 1\n",
    "            while left < right:\n",
    "                if t[left] != t[right]:\n",
    "                    sumCount += 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "        minCount = min(minCount, sumCount)\n",
    "    return minCount\n",
    "\n",
    "@cache \n",
    "def dp(s, k):\n",
    "    n = len(s)\n",
    "    if k == 0: \n",
    "        return getCount(s)\n",
    "    c = inf\n",
    "    for i in range(1, n - 2):\n",
    "        c = min(c, dp(s[i + 1:], k - 1) + getCount(s[:i + 1]))\n",
    "    return c\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        return dp(s, k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def rev(s):\n",
    "    n = len(s)\n",
    "    if n == 1:\n",
    "        return 0\n",
    "    res = float('inf')\n",
    "    for d in range(1, n):\n",
    "        if n % d != 0:\n",
    "            continue\n",
    "        st, ed = 0, (n - 1) // d * d\n",
    "        c = 0\n",
    "        for j in range(d):\n",
    "            t = st + j\n",
    "            e = ed + j\n",
    "            while t < e:\n",
    "                if s[t] != s[e]:\n",
    "                    c += 1\n",
    "                t += d\n",
    "                e -= d\n",
    "        res = min(res, c)\n",
    "    return res\n",
    "\n",
    "@cache\n",
    "def sol(s, k):\n",
    "    if k == 1:\n",
    "        return rev(s)\n",
    "    n = len(s)\n",
    "    res = float('inf')\n",
    "    for i in range(2, n - 1):\n",
    "        s1, s2 = s[:i], s[i:]\n",
    "        c1 = rev(s1)\n",
    "        res = min(res, c1 + sol(s2, k - 1))\n",
    "    return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        return sol(s, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX_N = 1 << 30\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        return self.dp(s, len(s) - 1, k)\n",
    "\n",
    "    @functools.cache\n",
    "    def dp(self, s: str, end: int, k: int) -> int:\n",
    "        if k == 1:\n",
    "            return self.count(s, 0, end)\n",
    "        ans = MAX_N\n",
    "        for start in range(1, end + 1):\n",
    "            ans = min(ans, self.dp(s, start - 1, k - 1) + self.count(s, start, end))\n",
    "        return ans\n",
    "\n",
    "    @functools.cache\n",
    "    def count(self, s: str, start: int, end: int):\n",
    "        s = s[start:end + 1]\n",
    "        if len(s) == 1:\n",
    "            return MAX_N\n",
    "        ret = MAX_N\n",
    "        for d in range(1, len(s)):\n",
    "            if not len(s) % d == 0:\n",
    "                continue\n",
    "            ans = 0\n",
    "            for i in range(d):\n",
    "                cur = s[i::d]\n",
    "                for j in range(len(cur) // 2):\n",
    "                    if cur[j] != cur[-(j + 1)]:\n",
    "                        ans += 1\n",
    "                if ans >= ret: break\n",
    "            ret = min(ret, ans)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        def cal(s1,s2):\n",
    "            c = 0\n",
    "            n = len(s1)\n",
    "            for i in range(n//2):\n",
    "                if s1[i] != s2[i]:\n",
    "                    c += 1\n",
    "            return c\n",
    "\n",
    "        def check(s):  # 判断半回文\n",
    "            n = len(s)\n",
    "            if n == 1:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            for k in range(1, n// 2+1 ):\n",
    "                if n % k == 0:\n",
    "                    # for j in range(k):\n",
    "                    c = sum(cal(s[j::k], s[j::k][::-1]) for j in range(k))\n",
    "                    # if all(s[j::k] == s[j::k][::-1] for j in range(k)):\n",
    "                    if c == 0:\n",
    "                        return 0\n",
    "                    ans = min(ans, c)\n",
    "            return ans\n",
    "        @cache\n",
    "        def dfs(st, end, k):#st 字符开始id end 字符结束id k:分段数量\n",
    "            if end > n-1:   #s用完了\n",
    "                return inf\n",
    "            if k == 1:\n",
    "                return check(s[st:])\n",
    "            if n - end + 1 < 2*k:   ##限制一下剩下的字符数,可以大幅缩减时间,毕竟dfs, 让结果自己算成inf来筛太费事了\n",
    "                return inf \n",
    "            return min(dfs(st, end+1, k) , dfs(end+1,end+2 , k-1)+ check(s[st:end+1]))\n",
    "        n = len(s)\n",
    "        ##调试\n",
    "        # print(check('ab'),check('bcac'),check('bcbc'), check('abcefz'))\n",
    "        return(dfs(0,0,k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        # 直接暴力起手解决问题，既然可以半回文，肯定是去最大的d，因为这样概率最大\n",
    "        # 数据范围比较小 2  <= s.length <= 200\n",
    "        @cache\n",
    "        def count(s):\n",
    "            ans = 0\n",
    "            i, j = 0, len(s)-1\n",
    "            while i < j:\n",
    "                ans += int(s[i] != s[j])\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return ans\n",
    "        \n",
    "        @cache\n",
    "        def g(s):\n",
    "            mi = inf\n",
    "            n = len(s)\n",
    "            for t in range(1, n):\n",
    "                if n % t == 0:\n",
    "                    cnt = 0\n",
    "                    for k in range(t):\n",
    "                        s1 = ''.join(s[i] for i in range(k, n, t))\n",
    "                        cnt += count(s1)\n",
    "                    mi = min(mi, cnt)\n",
    "            return mi\n",
    "        \n",
    "        @cache\n",
    "        def f(i, k):\n",
    "            if i >= len(s):\n",
    "                return 0 if k == 0 else inf\n",
    "            if k == 0:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            for j in range(i, len(s)):\n",
    "                v = g(s[i:j+1]) + f(j+1, k-1)\n",
    "                ans = min(ans, v)\n",
    "            return ans\n",
    "        \n",
    "        return f(0, k)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        @cache\n",
    "        def minSub(i, j, d):\n",
    "            if i == j or i + d == j:\n",
    "                return 0\n",
    "            r = sum(c1 != c2 for c1, c2 in zip(s[i:i+d], s[j-d:j])) + minSub(i + d, j - d, d)\n",
    "            #print(\"minSub(\", i, j, d, \"):\", r)\n",
    "            return r\n",
    "\n",
    "        @cache\n",
    "        def minSubAll(i, j):\n",
    "            return min(minSub(i, j, d) for d in range(1, j - i) if (j - i) % d == 0)\n",
    "\n",
    "        @cache\n",
    "        def minMulti(j, k):\n",
    "            if j == 0 and k == 0:\n",
    "                return 0\n",
    "            elif j < 2:\n",
    "                return float('inf')\n",
    "            else:\n",
    "                r = min(minMulti(i, k - 1) + minSubAll(i, j) for i in range(0, j - 1))\n",
    "                #print(\"minMulti(\", j, k, \"):\", r)\n",
    "                return r\n",
    "        return minMulti(len(s), k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumChanges(self, s: str, k: int) -> int:\n",
    "        div = defaultdict(lambda: [1])\n",
    "        n = len(s)\n",
    "        for d in range(2, n):\n",
    "             for v in range(d + d, n + 1, d):\n",
    "                div[v].append(d)\n",
    "\n",
    "        @cache\n",
    "        def change(i, j):\n",
    "            if i + 1 >= j: return inf\n",
    "            res = inf\n",
    "            for d in div[j - i]:\n",
    "                res = min(res, semi(i, j, d))\n",
    "            return res\n",
    "\n",
    "        @cache\n",
    "        def semi(i, j, d):\n",
    "            if i >= j: return 0\n",
    "            res = semi(i + d, j - d, d)\n",
    "            for ii in range(d):\n",
    "                if s[i + ii] != s[j - d + ii]:\n",
    "                    res += 1\n",
    "            return res\n",
    "\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k == 1:\n",
    "                return change(0, i)\n",
    "            res = inf\n",
    "            for j in range((k - 1) * 2, i):\n",
    "                cur = dp(j, k - 1) + change(j, i)\n",
    "                res = min(res, cur)\n",
    "            return res\n",
    "\n",
    "        return dp(n, k)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
